#include <vector>
#include <algorithm>

using namespace std;
class Solution
{
public:
    vector<vector<int>> combinationSum2(vector<int> &candidates, int target)
    {
        vector<pair<int, int>> freq;
        sort(candidates.begin(), candidates.end());
        int size = candidates.size();
        for (int i = 0; i < size; i++)
        {
            if (freq.empty() || freq.back().first != candidates[i])
            {
                freq.emplace_back(candidates[i], 1);
            }
            else
            {
                freq.back().second++;
            }
        }
        vector<vector<int>> ans;
        vector<int> comb;
        solve(freq, ans, 0, 0, target, comb);
        return ans;
    }
    void solve(vector<pair<int, int>> &freq, vector<vector<int>> &ans, int index, int sum, int target, vector<int> &comb)
    {
        int count;
        int size = freq.size();
        if (index >= size)
        {
            return;
        }
        count = 0;
        while (count < freq[index].second)
        {
            if (sum + freq[index].first <= target)
            {
                sum += freq[index].first;
                count++;
                comb.push_back(freq[index].first);
                if (sum == target)
                {
                    ans.push_back(comb);
                    break;
                }
                solve(freq, ans, index + 1, sum, target, comb);
            }
            else
            {
                break;
            }
        }
        while (count-- > 0)
        {
            comb.pop_back();
            sum -= freq[index].first;
        }
        solve(freq, ans, index + 1, sum, target, comb);
    }
};
int main(int argc, char const *argv[])
{
    vector<int> candidates = {4, 4, 2, 1, 4, 2, 2, 1, 3};
    int t = 6;
    Solution s;
    vector<vector<int>> ans = s.combinationSum2(candidates, t);
    ans[0];
    return 0;
}
